#include<bits/stdc++.h>
using namespace std;

#define N 500050
#define M 500050
int f[N], nxt[N], last[N], n, m, a[N];

struct node{
    int l, r, ans, id;
}q[M];

int lowbit(int x){
    return x & (-x);
}

void add(int x, int k){
    for(int i = x; i <= n; i += lowbit(i)) {
        f[i] += k;
    }
}

int get(int x){
    int res = 0;
    for(int i = x; i; i -= lowbit(i)){
        res += f[i];
    }
    return res;
}

bool cmp(node a, node b){
    if(a.l == b.l) return a.r < b.r;
    else return a.l < b.l;
}
bool cmp1(node a, node b){
    return a.id < b.id;
}

int main(){
    cin>>n>>m;
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        nxt[i] = n + 1;
        if(!last[a[i]]) last[a[i]] = i, add(i, 1);
        else nxt[last[a[i]]] = i, last[a[i]] = i;
    }
    for(int i = 1; i <= m; i++){
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id = i;
    }
    sort(q + 1, q + 1 + m, cmp);
    int cur = 1;
    for(int l = 1; l <= n; l++){
        while(q[cur].l == l && cur <= m){
            // cout<<cur<<endl;
            q[cur].ans = get(q[cur].r) - get(q[cur].l - 1);
            cur++;
        }
        // cout<<nxt[l]<<endl;
        add(l, -1); add(nxt[l], 1);
    }
    sort(q + 1, q + 1 + m, cmp1);
    for(int i = 1; i <= m; i++){
        printf("%d\n", q[i].ans);
    }
    return 0;
}
